#include <stdio.h>
#include <stdlib.h>
#include <tchar.h>

#include "getopt.h"

#include "IncidenceGraph.h"
#include "GraphReader.h"
#include "Dijkstra.h"
#include "Stopwatch.h"


static struct global_args_t {
	bool	graph_flag;
	bool	path_flag;
	bool	iteration_flag;
	bool	repeat_flag;
	int		repeats;
	bool	source_flag;
	int		source;
	bool	target_flag;
	int		target;
	bool	batch_flag;
	char*	batch_filename;
	char*	graph_filename;
} global_args;


void usage()
{
	//         "---------|---------|---------|---------|---------|---------|---------|"
	cout << _T("usage: dijkstra [-v] [-b] [-i] [-s source] [-t target] graph_file") << endl;
	cout << _T("  -g            Print graph structure.") << endl;
	cout << _T("  -p            Print paths.") << endl;
	cout << _T("  -i            Print iterations.") << endl;
	cout << _T("  -r count      Reapeat search 'count' times and calculate average") << endl;
	cout << _T("                time. Iteration flag is ignored if repeat is set.") << endl;
	cout << _T("  -s source     Source vertex for Dijkstra's algorithm. If source is") << endl;
	cout << _T("                not defined, the program only prints the graph") << endl;
	cout << _T("                structure.") << endl;
	cout << _T("  -t target     Target vertex. If target is defined the program only") << endl;
	cout << _T("                prints the path to target.") << endl;
	cout << _T("  -b file       Read list of input files from the specified file.") << endl;
}


void print_graph(IncidenceGraph& g, bool graph_flag)
{
	auto vertices = g.GetVertices();

	cout.width(0);
	cout.precision(3);
	cout << _T("|V|=") << g.VertexCount() << _T("  |E|=") << g.EdgeCount() << _T("  D=") << g.Density() << endl;
	
	if (graph_flag) {
		for (auto it = vertices.begin(); it != vertices.end(); it++) {
			cout << _T("vertex ") << it->i << ": " << g.EdgeCount(it->i) << _T(" neighbors") << endl;

			auto e = g.GetEdges(it->i);
			for (auto itt = e.begin(); itt != e.end(); itt++) {
					cout << "    " << itt->i << _T(" -> ") << itt->j << _T(" (") << itt->weight << _T(")") << endl;
			}
		}
	}
}


void print_single_path(Dijkstra& d, int target, bool path_flag)
{
	auto path = d.GetShortestPath(target);

	cout.width(0);
	cout.precision(3);
	cout << _T("    ") << d.Source() << _T(" -> ") << target << _T(" (") << d.GetDistance(target) << _T("):  ");
	for (auto itt = path.begin(); itt != path.end(); itt++) {
			cout << itt->current << _T("  ");
	}
	cout << endl;
}


void print_all_paths(Dijkstra& d, bool path_flag)
{
	auto distances = d.GetDistances();
	auto source = d.Source();

	for (auto it = distances.begin(); it != distances.end(); it++) {
		auto path = d.GetShortestPath(it->current);
		cout.width(0);
		cout.precision(3);
		cout << _T("    ") << source << _T(" -> ") << it->current << _T(" (") << d.GetDistance(it->current) << _T("):  ");
		for (auto itt = path.begin(); itt != path.end(); itt++) {
				cout << itt->current << _T("  ");
		}
		cout << endl;
	}
}


void print_paths(Dijkstra& d, bool path_flag, int target, bool target_flag)
{
	cout.width(0);
	cout << _T("S=") << d.Source() << _T("  |P|=") << d.GetPathCount() << endl;

	if (path_flag) {
		if (target_flag)
			print_single_path(d, target, path_flag);
		else
			print_all_paths(d, path_flag);
	}
}


void dijkstra_listener(
	int							iteration,
	DijkstraStage				stage,
	const map<int, PathVertex>*	paths,
	const map<int, bool>*		unvisited,
	int							current,
	int							neighborCount,
	int							neighbor,
	double						distanceToCurrent,
	double						oldDistanceToNeighbor,
	double						newDistanceToNeighbor)
{
	switch (stage) {
	case NEXT_ITERATION:
		cout.width(72);
		cout.fill(_T('-'));
		cout << _T("") << endl;
		cout.fill(_T(' '));
		cout.width(12);
		cout << left << iteration;
		break;
	case LAST_ITERATION:
		cout << endl;
		break;
	case FIND_SHORTEST_UNVISITED:
		cout.width(12);
		cout << left << current << distanceToCurrent << endl;
		break;
	case VISIT_CONNECTED_EDGES:
		break;
	case UPDATE_DISTANCE:
		cout.width(36);
		cout << _T("");
		cout.width(12);
		cout << left << neighbor;
		cout.width(12);
		if (oldDistanceToNeighbor <= DBL_MAX && oldDistanceToNeighbor >= -DBL_MAX)
			cout << left << oldDistanceToNeighbor;
		else
			cout << left << _T("-");
		cout.width(12);
		cout << left << newDistanceToNeighbor << endl;
		break;
	};
}


int process_file(const string filename)
{
	Stopwatch stopwatch;

	auto g = IncidenceGraph();
    auto reader = GraphReader(g);

	cout.width(0);
	cout << filename << endl;

	cout.width(24);
	cout << left << _T("loading graph...");

	stopwatch.Start();
    if (!reader.Read(filename)) {
		cout << endl;
		cout << _T("ERROR -- not a valid graph file, or file not found");
		exit(1);
	}
	stopwatch.Stop();
	
	cout.precision(3);
	cout << stopwatch.ElapsedSeconds() << _T(" seconds") << endl;

	print_graph(g, global_args.graph_flag);

	if (!global_args.source_flag)
		return 0;

	cout.width(24);
	cout << left << _T("calculating paths...");

	Dijkstra dijkstra;
	if (global_args.iteration_flag && !global_args.repeat_flag) {
		cout << endl;
		//          -----------|-----------|-----------|-----------|-----------|-----------|
		cout << _T("iteration   current     distance    neighbor    old_dist    new_dist") << endl;
		dijkstra.Listener(dijkstra_listener);
	}

	double seconds = 0;
	bool success = false;
	for (int i = 0; i < global_args.repeats; i++) {
		stopwatch.Start();
		success = dijkstra.CalculateShortestDistances(&g, global_args.source);
		stopwatch.Stop();
		seconds += stopwatch.ElapsedSeconds();
	}
	seconds /= (double) global_args.repeats;

	cout.precision(3);
	cout << seconds << _T(" seconds (average of ") << global_args.repeats << _T(" repeats)") << endl;

	if (success)
		print_paths(dijkstra, global_args.path_flag, global_args.target, global_args.target_flag);
	else
		cout << _T("failed to calculate shortest paths") << endl;

	return 0;
}


int main(int argc, char **argv)
{
	static const char *opt_string = _T("gpir:s:t:b:h?");

	global_args.graph_flag			= false;
	global_args.path_flag			= false;
	global_args.iteration_flag		= false;
	global_args.repeat_flag			= false;
	global_args.repeats				= 1;
	global_args.source_flag			= false;
	global_args.source				= -1;
	global_args.target_flag			= false;
	global_args.target				= -1;
	global_args.batch_flag			= false;
	global_args.batch_filename		= "";
	global_args.graph_filename		= "";

	int opt = 0;
	opt = getopt(argc, argv, opt_string);

	while (opt != -1) {
		switch(opt) {
		case _T('g'):
			global_args.graph_flag = true;
			break;

		case _T('p'):
			global_args.path_flag = true;
			break;

		case _T('i'):
			global_args.iteration_flag = true;
			break;

		case _T('r'):
			global_args.repeat_flag = true;
			global_args.repeats = atoi(optarg);
			break;

		case _T('s'):
			global_args.source_flag = true;
			global_args.source = atoi(optarg);
			break;

		case _T('t'):
			global_args.target_flag = true;
			global_args.target = atoi(optarg);
			break;

		case _T('b'):
			global_args.batch_flag = true;
			global_args.batch_filename = optarg;
			break;

		case _T('h'):
		case _T('?'):
			usage();
			exit(0);
			break;

		default:
			abort();
		}

		opt = getopt(argc, argv, opt_string);
	}

	if (!global_args.batch_flag && optind == argc) {
		usage();
		exit(1);
	}
	else {
		global_args.graph_filename = argv[optind];
    }

	int rc = 0;

	if (global_args.batch_flag) {
		ifstream ifs(global_args.batch_filename, Ifstream::in);
		while (ifs.good()) {
			string filename;
			getline(ifs, filename);
			if (filename.find_first_not_of(_T(' ')) != string::npos) {
				rc = process_file(filename);
				if (rc) return rc;
			}
		}
	}
	else {
		return process_file(global_args.graph_filename);
	}
	

    return 0;
}